#pragma once

#include <vector>
#include <map>
#include <utility>
namespace BWSAL
{
  /**
   * An associated heap class with the ability to read and change the values
   * of arbitrary objects in the heap.
   * Note: Objects in the heap must be unique, however any number of objects
   * can have the same value
   */
  template < class _Tp, class _Val > 
  class Heap
  {
    private :
    /** Heap data, stored as a vector */
    std::vector< std::pair< _Tp, _Val > > data;

    /** Maps objects to their positions in the data vector */
    std::map< _Tp, int > mapping;

    /** True if the heap is a min heap, otherwise the heap is a max heap*/
    bool minHeap;

    /**
     * Percolates the given element in the heap up
     * @param the index of the element to percolate up
     * @return the final index of the element, after percolation is complete
     */
    int percolate_up( int index );

    /**
     * Percolates the given element in the heap down
     * @param the index of the element to percolate down
     * @return the final index of the element, after percolation is complete
     */
    int percolate_down( int index );

    public :
    Heap( bool isMinHeap = false ) : minHeap( isMinHeap ) {}
    ~Heap() {}
    /**
     * Pushes an object associated with the given value onto the heap
     * @param The object - value pair to push onto the heap
     */
    void push( std::pair< _Tp, _Val > x );
    /**
     * Pops the top of the heap
     */
    void pop();
    /**
     * Returns a reference to the object - value pair at the top of the heap
     */
    const std::pair< _Tp, _Val >& top() const;
    /**
     * Updates the given object with the given value and moves the
     * object to the appropiate place in the heap
     * @param an object that exists in the heap
     * @param the new value for that object
     * @return boolean based on the success of the update
     */
    bool set( _Tp& x, _Val v );
    /**
     * Looks up the given object and returns its value
     * @param object to look up
     * @return the value of the object
     */
    const _Val& get( _Tp& x ) const;

    /**
     * Returns true if the heap contains the given element, false otherwise
     */
    bool contains( _Tp& x ) const;

    /**
     * Returns true if the heap has no elements, false otherwise
     */
    bool empty() const;
    /**
     * Returns the number of elements in the heap
     */
    int size() const;
    /**
     * Removes all of the elements in the heap
     */
    void clear();
    /**
     * Deletes the given object from the heap
     * @param an object that already exists in the heap
     * @return boolean based on the success of the deletion
     */
    bool erase( _Tp& x );
  };

  // ------------------------------- PERCOLATE UP---------------------------------
  template < class _Tp, class _Val >
  int Heap< _Tp, _Val >::percolate_up( int index )
  {
    if ( index < 0 || index >= (int)data.size() )
    {
      return -1;
    }
    unsigned int parent = ( index - 1 ) / 2;
    int m = 1;
    if ( this->minHeap )
    {
      m = -1;
    }
    while ( index > 0 && m * data[parent].second < m * data[index].second )
    {
      std::pair< _Tp, _Val > temp = data[parent];
      data[parent] = data[index];
      data[index] = temp;
      ( *mapping.find( data[index].first ) ).second = index;
      index = parent;
      parent = ( index - 1 ) / 2;
    }
    ( *mapping.find( data[index].first ) ).second = index;
    return index;
  }

  // ------------------------------ PERCOLATE DOWN--------------------------------
  template < class _Tp, class _Val >
  int Heap< _Tp, _Val >::percolate_down( int index )
  {
    if ( index < 0 || index >= (int)data.size() )
    {
      return -1;
    }
    unsigned int lchild = index*2 + 1;
    unsigned int rchild = index*2 + 2;
    unsigned int mchild;
    int m = 1;
    if ( this->minHeap )
    {
      m = -1;
    }
    while ( ( data.size() > lchild && m * data[index].second < m * data[lchild].second ) ||
      ( data.size() > rchild && m * data[index].second < m * data[rchild].second ) )
    {
      mchild = lchild;
      if ( data.size() > rchild && m * data[rchild].second > m * data[lchild].second )
      {
        mchild = rchild;
      }
      std::pair< _Tp, _Val > temp = data[mchild];
      data[mchild] = data[index];
      data[index] = temp;
      ( *mapping.find( data[index].first ) ).second = index;
      index = mchild;
      lchild = index * 2 + 1;
      rchild = index * 2 + 2;
    }
    ( *mapping.find( data[index].first ) ).second = index;
    return index;
  }
  // ----------------------------------- PUSH-------------------------------------
  template < class _Tp, class _Val >
  void Heap< _Tp, _Val >::push( std::pair< _Tp, _Val > x )
  {
    int index = data.size();
    if ( mapping.insert( std::make_pair( x.first, index ) ).second )
    {
      data.push_back( x );
      percolate_up( index );
    }
  }

  // ----------------------------------- POP--------------------------------------
  template < class _Tp, class _Val >
  void Heap< _Tp, _Val >::pop()
  {
    if ( data.empty() )
    {
      return;
    }
    mapping.erase( data.front().first );
    data.front() = data.back();
    data.pop_back();
    if ( data.empty() )
    {
      return;
    }
    std::map< _Tp, int >::iterator iter = mapping.find( data.front().first );
    if ( iter != mapping.end() )
    {
      ( *iter ).second = 0;
      percolate_down( 0 );
    }
  }

  // ----------------------------------- TOP--------------------------------------
  template < class _Tp, class _Val >
  const std::pair< _Tp, _Val >& Heap< _Tp, _Val >::top() const
  {
    return data.front();
  }

  // ---------------------------------- EMPTY-------------------------------------
  template < class _Tp, class _Val >
  bool Heap< _Tp, _Val >::empty() const
  {
    return data.empty();
  }

  // ----------------------------------- SET--------------------------------------
  template < class _Tp, class _Val >
  bool Heap< _Tp, _Val >::set( _Tp& x, _Val v )
  {
    std::map< _Tp, int >::iterator iter = mapping.find( x );
    if ( iter == mapping.end() )
    {
      push( std::make_pair( x, v ) );
      return true;
    }
    int index = ( *iter ).second;
    data[index].second = v;
    index = percolate_up( index );
    if ( index >= 0 && index < (int)data.size() )
    {
      percolate_down( index );
      return true;
    }
    return false;
  }

  // ----------------------------------- GET--------------------------------------
  template < class _Tp, class _Val >
  const _Val& Heap< _Tp, _Val >::get( _Tp& x ) const
  {
    std::map< _Tp, int >::const_iterator iter = mapping.find( x );
    int index = ( *iter ).second;
    return data[index].second;
  }

  // --------------------------------- CONTAINS-----------------------------------
  template < class _Tp, class _Val >
  bool Heap< _Tp, _Val >::contains( _Tp& x ) const
  {
    std::map< _Tp, int >::const_iterator iter = mapping.find( x );
    return ( iter != mapping.end() );
  }

  // ---------------------------------- SIZE--------------------------------------
  template < class _Tp, class _Val >
  int Heap< _Tp, _Val >::size() const
  {
    return data.size();
  }

  // ---------------------------------- CLEAR-------------------------------------
  template < class _Tp, class _Val >
  void Heap< _Tp, _Val >::clear()
  {
    data.clear();
    mapping.clear();
  }

  // ---------------------------------- ERASE-------------------------------------
  template < class _Tp, class _Val >
  bool Heap< _Tp, _Val >::erase( _Tp& x )
  {
    std::map< _Tp, int >::iterator iter = mapping.find( x );
    if ( iter == mapping.end() )
    {
      return false;
    }
    if ( data.size() == 1 )
    {
      this->clear();
    }
    else
    {
      int index = ( *iter ).second;
      data[index] = data.back();
      data.pop_back();
      mapping.erase( iter );
      percolate_down( index );
    }
    return true;
  }
  // ------------------------------------------------------------------------------
}